package com.klun.project.common.constans.leetcode;

import com.klun.project.common.constans.utils.ParseUtils;

import java.util.ArrayList;
import java.util.List;

// 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
// 回文串 是正着读和反着读都一样的字符串。
// 示例 1：
// 输入：s = "aab"
// 输出：[["a","a","b"],["aa","b"]]
// 示例 2：
// 输入：s = "a"
// 输出：[["a"]]
// 提示：
// 1 <= s.length <= 16
// s 仅由小写英文字母组成
// Related Topics 字符串 动态规划 回溯
// 👍 1297 👎 0

public class Solution131 {

	// f(i,j) = f(i-1,j+1) && s(i) == s(j)

	public List<List<String>> partition(String s) {
		List<List<String>> res = new ArrayList<>();
		int len = s.length();
		String[][] dp = new String[len][len];
		dp[0][0] = "";
		for (int end = 0; end < s.length(); end++) {
			char endChar = s.charAt(end);
			for (int begin = 0; begin < end; begin++) {
				if (endChar == s.charAt(begin) && dp[begin + 1][end - 1] != null) {
					dp[begin][end] = s.substring(begin, end);
				}
			}
		}
		List<String> ans = new ArrayList<>();
		dfs(s, 0, res, dp, ans, len);
		return res;
	}

	public void dfs(String s, int i, List<List<String>> res, String[][] dp, List<String> ans, int len) {
		if (i == len) {
			res.add(new ArrayList<String>(ans));
			return;
		}
		for (int j = i; j < len; ++j) {
			if (dp[i][j] != null) {
				ans.add(s.substring(i, j + 1));
				dfs(s, j + 1, res, dp, ans, len);
				ans.remove(ans.size() - 1);
			}
		}
	}

//
//	public List<String> dfs(String[][] dp, int begin, int end, List<List<String>> res) {
//		String[] strings = dp[begin];
//		for (int i = 0; i < end; i++) {
//			if (strings[i] != null) {
//				List<String> ls = new ArrayList<>();
//				res.add(strings[i]);
//				dfs(dp, i, end, res);
//			}
//			if (i == end) {
//				res.add();
//			}
//		}
//		return res;
//	}

	public static void main(String[] args) {
		Solution131 solution = new Solution131();
		List<List<Integer>> arrayLists = ParseUtils.stringToIntLists("[[2],[3,4],[6,5,7],[4,1,8,3]]");
		System.out.println(solution.partition("afsahihuidsafho"));
	}

}
